import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* @description: 面试题 17.19. 消失的两个数字
* @author hewei
* @date 2022/9/26 14:16
* @version 1.0
*/

public class MissingTwo {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new MissingTwo().missingTwo(new int[]{2, 3})));
    }

    public int[] missingTwo1(int[] nums) {
        int one = 0;
        int two = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == -1) continue;
            if (nums[i] - 1 < nums.length) {
                int index = nums[i] - 1;
                while (index < nums.length && nums[index] != -1) {
                    int temp = index;
                    index = nums[index] - 1;
                    nums[temp] = -1;
                }
                if (index == nums.length) {
                    one = -1;
                } else if (index == nums.length + 1) {
                    two = -1;
                }
            } else if (nums[i] - 1 == nums.length) {
                one = -1;
            } else two = -1;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != -1) list.add(i + 1);
        }
        if (one != -1) list.add(nums.length + 1);
        if (two != -1) list.add(nums.length + 2);
        return new int[]{list.get(0), list.get(1)};
    }

    public int[] missingTwo2(int[] nums) {
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp ^= nums[i];
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            temp ^= i;
        }
        int oneBit = Integer.lowestOneBit(temp);
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if ((num & oneBit) == 0) {
                a ^= num;
            } else b ^= num;
        }
        for (int i = 1; i <= nums.length + 2; i++) {
            if ((i & oneBit) == 0) {
                a ^= i;
            } else b ^= i;
        }
        return new int[]{a, b};
    }

    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int delta = (1 + n) * n / 2 - sum;
        int temp = delta / 2;
        int count = 0;
        for (int num : nums) {
            if (num <= temp) count += num;
        }
        int one = (1 + temp) * temp / 2 - count;
        return new int[]{one, delta - one};
    }
}
